package _07_priority_queue.my_implements;

import _00_my.exception.TechnicalLimitationException;
import _04_queue.AbstractQueue;
import _07_priority_queue.Priority;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/8 - 1:08
 * 基于无序数组实现优先级队列（往尾部插入，弹出时需要迭代找到优先级最高的元素）
 * 每次弹出优先级最高的元素
 * 适用于入队操作多于出队的场景
 * O(n)
 */

public class PriorityQueue1<E extends Priority> extends AbstractQueue<E> {
    Priority[] data;
    int size;
    int capacity;

    public PriorityQueue1(int capacity) {
        data = new Priority[this.capacity = capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        data[size++] = e;
        return true;
    }

    /**
     * 将指定下标的元素移除，数组整体向后移动
     *
     * @param i
     */
    void remove(int i) {
        if (i != size - 1) {
            System.arraycopy(data, i + 1, data, i, data.length - i - 1);
        }
        data[--size] = null;
    }

    /**
     * 获取数组中优先级最高的元素下标
     *
     * @return
     */
    int getMaxPriority() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (data[i].priority() > data[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = getMaxPriority();
        E e = (E) data[max];
        remove(max);
        return e;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) data[getMaxPriority()];
    }

//    @Override
//    public boolean isEmpty() {
//        return size == 0;
//    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        throw new TechnicalLimitationException();
    }
}
